"""
链表和列表相比的优势：
1、链表在插入和删除的操作上明显快于顺序表
2、链表的内存可以更灵活的分配
3、链表这种链式存储的数据结构对树和图的结构有很大启发性
"""

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None


class Linklist:
    def __init__(self, li, method='head'):
        self.head = None
        self.tail = None
        if method == 'head':
            self.creat_linklist_head(li)
        elif method == 'tail':
            self.creat_linklist_tail(li)
        else:
            raise ValueError("Unsupport value %s" % method)

    def creat_linklist_head(self, li):  # 头插法
        self.head = Node(0)
        for v in li:
            n = Node(v)
            n.next = self.head.next
            self.head.next = n
            self.head.data += 1

    def creat_linklist_tail(self, li):
        self.head = Node(0)
        self.tail = self.head
        for v in li:
            p = Node(v)
            self.tail.next = p
            self.tail = p
            self.head.data += 1

    def traverse_linklist(self):
        p = self.head.next
        while p:
            print(p.data)
            p = p.next

    def __len__(self):
        return self.head.data


ll = Linklist([1, 2, 3, 4, 5], method='tail')
ll.traverse_linklist()


"""
插入
p.next = curNode.next
curNode.next = p
删除
p = curNode.next  先把需要删除的节点存起来，最后再删除
curNode.next = curNode.next.next
del p
"""


"""
双链表
定义节点：
class Node(object):
    def __init__(self, item = None):
        self.item = item
        self.next = None
        self.prior = None
        
插入
p.next = curNode.next
curNode.next.prior = p
p.prior = curNode
curNode.next = p

删除
p = curNode.next
curNode.next = p.next
p.next.prior = curNode
del p
"""